/*
 * Copyright (C) 2011 Nicola Bonzanni
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package nl.vu.few.ibivu.jlemon.listgraph;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Set;

import nl.vu.few.ibivu.jlemon.AbstractGraph;
import nl.vu.few.ibivu.jlemon.WeakHashSet;
import nl.vu.few.ibivu.jlemon.concepts.AddArcHandler;
import nl.vu.few.ibivu.jlemon.concepts.AddEdgeHandler;
import nl.vu.few.ibivu.jlemon.concepts.AddNodeHandler;
import nl.vu.few.ibivu.jlemon.concepts.ClearHandler;
import nl.vu.few.ibivu.jlemon.concepts.EraseArcHandler;
import nl.vu.few.ibivu.jlemon.concepts.EraseEdgeHandler;
import nl.vu.few.ibivu.jlemon.concepts.EraseNodeHandler;
import nl.vu.few.ibivu.jlemon.concepts.HasAddArcHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasAddEdgeHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasAddNodeHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasClearHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasEdge;
import nl.vu.few.ibivu.jlemon.concepts.HasEraseArcHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasEraseEdgeHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasEraseNodeHandlers;
import nl.vu.few.ibivu.jlemon.concepts.IncidentEdgeIterator;

public class ListGraph extends AbstractGraph<Node, ListGraph.Edge, ListGraph.Arc>
		implements HasAddNodeHandlers<Node>, HasEraseNodeHandlers<Node>,
		HasAddEdgeHandlers<ListGraph.Edge>, HasEraseEdgeHandlers<ListGraph.Edge>,
		HasAddArcHandlers<ListGraph.Arc>, HasEraseArcHandlers<ListGraph.Arc>,
		HasClearHandlers, Serializable {

	private static final long serialVersionUID = 1L;
	private int nodeNum;
	private int arcNum;
	private int edgeNum;

	// FIXME handlers sets are not correctly restored after serialization because WeakHashSet are not serializable
	// since the WeakHashMap they use is not serializable as well
	transient private Set<AddNodeHandler<Node>> addNodeHandlers = new WeakHashSet<AddNodeHandler<Node>>();
	transient private Set<EraseNodeHandler<Node>> eraseNodeHandlers = new WeakHashSet<EraseNodeHandler<Node>>();
	transient private Set<AddArcHandler<Arc>> addArcHandlers = new WeakHashSet<AddArcHandler<Arc>>();
	transient private Set<EraseArcHandler<Arc>> eraseArcHandlers = new WeakHashSet<EraseArcHandler<Arc>>();
	transient private Set<AddEdgeHandler<Edge>> addEdgeHandlers = new WeakHashSet<AddEdgeHandler<Edge>>();
	transient private Set<EraseEdgeHandler<Edge>> eraseEdgeHandlers = new WeakHashSet<EraseEdgeHandler<Edge>>();
	transient private Set<ClearHandler> clearHandlers = new WeakHashSet<ClearHandler>();

	/*
	 * Using integers over pointers lead to save at least 50% of the space on
	 * 64bit JVMs.
	 */
	private int firstFreeArc = -1;
	private int firstFreeNode = -1;
	private int firstNode = -1;

	/*
	 * On one hand, internal structure are needed because we don't want to risk
	 * to remove a node that belongs to another graph. Internal node keep save
	 * the internal list structure of nodes and arcs.
	 * 
	 * On the other hand, we need to keep the reference to the "external" node
	 * object in order to avoid excessive object creation and excessively use
	 * GC.
	 */
	@SuppressWarnings("serial")
	private class InternalNode implements Serializable {
		Node node = new Node();
		int firstOut = -1;
		int previous = -1;
		int next = -1;

		public InternalNode(int id) {
			node.id = id;
		}

		public Node getNode() {
			return node;
		}
	}

	@SuppressWarnings("serial")
	private class InternalArc implements Serializable {
		Arc arc = new Arc();
		int target = -1;
		int previousOut = -1;
		int nextOut = -1;

		public InternalArc(int id) {
			arc.id = id;
		}

		public Arc getArc() {
			return arc;
		}
	}

	private ArrayList<InternalNode> nodes = new ArrayList<InternalNode>();
	private ArrayList<InternalArc> arcs = new ArrayList<InternalArc>();
	
	public void ensureNodesCapacity(int minCapacity) {
		nodes.ensureCapacity(minCapacity);
	}
	
	public void ensureArcsCapacity(int minCapacity) {
		arcs.ensureCapacity(minCapacity);
	}

	@Override
	public Node u(Edge edge) {
		return nodeFromId(arcs.get(2 * edge.id).target);
	}

	@Override
	public Node v(Edge edge) {
		return nodeFromId(arcs.get(2 * edge.id + 1).target);
	}

	@Override
	public Node source(Arc arc) {
		return nodeFromId(arcs.get(arc.id ^ 1).target);
	}

	@Override
	public Node target(Arc arc) {
		return nodeFromId(arcs.get(arc.id).target);
	}

	@Override
	public int id(Node node) {
		if (valid(node))
			return node.id;
		return -1;
	}

	@Override
	public int id(Edge edge) {
		if (valid(edge))
			return edge.id;
		return -1;
	}

	@Override
	public int id(Arc arc) {
		if (valid(arc))
			return arc.id;
		return -1;
	}

	@Override
	public Node nodeFromId(int id) {
		if (validNodeId(id))
			return nodes.get(id).getNode();
		return null;
	}

	@Override
	public Edge edgeFromId(int id) {
		if (validEdgeId(id))
			return arcFromId(2 * id).edge();
		return null;
	}

	@Override
	public Arc arcFromId(int id) {
		if (validArcId(id))
			return arcs.get(id).getArc();
		return null;
	}

	@Override
	public int maxNodeId() {
		return nodes.size() - 1;
	}

	@Override
	public int maxEdgeId() {
		return nodes.size() / 2 - 1;
	}

	@Override
	public int maxArcId() {
		return arcs.size() - 1;
	}

	@Override
	public int nodeNum() {
		return nodeNum;
	}

	@Override
	public int arcNum() {
		return arcNum;
	}

	@Override
	public int edgeNum() {
		return edgeNum;
	}

	@Override
	public boolean direction(Arc arc) {
		// is and arc with an odd id? see addEdge()
		return (arc.id & 1) == 1;
	}

	@Override
	public Arc direct(Edge edge, boolean inherent) {
		return arcFromId(edge.id * 2 + (inherent ? 1 : 0));
	}

	@Override
	public Node firstNode() {
		return nodeFromId(firstNode);
	}

	@Override
	public Node next(Node node) {
		return nodeFromId(nodes.get(node.id).next);
	}

	@Override
	public Arc firstArc() {
		int n = firstNode;
		// cycle until we pass trough valid nodes without arcs
		while (n != -1 && nodes.get(n).firstOut == -1) {
			n = nodes.get(n).next;
		}
		return (n == -1) ? null : arcFromId(nodes.get(n).firstOut);
	}

	@Override
	public Arc next(Arc arc) {
		if (arcs.get(arc.id).nextOut != -1) {
			return arcFromId(arcs.get(arc.id).nextOut);
		} else {
			int n = nodes.get(arcs.get(arc.id ^ 1).target).next;
			// cycle until we pass trough valid nodes without arcs
			while (n != -1 && nodes.get(n).firstOut == -1) {
				n = nodes.get(n).next;
			}
			return (n == -1) ? null : arcFromId(nodes.get(n).firstOut);
		}
	}

	@Override
	public Edge firstEdge() {
		int a;
		int n = firstNode;
		while (n != -1) {
			a = nodes.get(n).firstOut;
			// get the next arc with even id
			// if a == -1 then ((a & 1) != 1) evaluate false
			while ((a & 1) != 1) {
				a = arcs.get(a).nextOut;
			}
			if (a != -1) {
				return arcFromId(a).edge();
			}
			n = nodes.get(n).next;
		}
		return null;
	}

	@Override
	public Edge next(Edge edge) {
		int a;
		// retrieve the target of this edge
		int n = arcs.get(edge.id * 2).target;
		// get the arc with the odd id representing this edge
		a = arcs.get((edge.id * 2) | 1).nextOut;
		// get the next arc with even id
		// if a == -1 then ((a & 1) != 1) evaluate false
		while ((a & 1) != 1) {
			a = arcs.get(a).nextOut;
		}
		if (a != -1) {
			return arcFromId(a).edge();
		}
		n = nodes.get(n).next;
		// start cycling through the nodes till we find a node
		// with arcs
		while (n != -1) {
			a = nodes.get(n).firstOut;
			while ((a & 1) != 1) {
				a = arcs.get(a).nextOut;
			}
			if (a != -1) {
				return arcFromId(a).edge();
			}
			n = nodes.get(n).next;
		}
		return null;
	}

	@Override
	public Arc firstOut(Node node) {
		return arcFromId(nodes.get(node.id).firstOut);
	}

	@Override
	public Arc nextOut(Arc arc) {
		return arcFromId(arcs.get(arc.id).nextOut);
	}

	@Override
	public Arc firstIn(Node node) {
		// get the opposite direction arc of firstOut
		// in fact, 2 ^ 1 = 3 and 3 ^ 1 = 2
		// if firstOut == -1 then firstOut ^ -1 evaluates -2
		return arcFromId((nodes.get(node.id).firstOut) ^ 1);
	}

	@Override
	public Arc nextIn(Arc arc) {
		// get the arc opposite to the given arc
		// since only outgoing arc are in a list
		// get the opposite (incoming) arc of the
		// nextOut arc
		// if nextOut == -1 then nextOut ^ -1 evaluates -2
		return arcFromId((arcs.get(arc.id ^ 1).nextOut) ^ 1);
	}

	@Override
	public Edge firstInc(IncidentEdgeIterator<Edge> iterator, Node node) {
		// get the id of the first arc outgoing of the give node
		int a = nodes.get(node.id).firstOut;
		Edge e;
		if (a != -1) {
			e = arcFromId(a).edge();
			// check if the first outgoing arc is inherently directed
			// that is it, it check if the id is odd
			iterator.setInherent(((a & 1) == 1));
		} else {
			e = null;
			iterator.setInherent(true);
		}
		return e;
	}

	@Override
	public Edge nextInc(IncidentEdgeIterator<Edge> iterator) {
		int a = (arcs.get((iterator.peek().id * 2) | (iterator.isInherent() ? 1 : 0)).nextOut);
		Edge e;
		if (a != -1) {
			e = arcFromId(a).edge();
			iterator.setInherent(((a & 1) == 1));
		} else {
			e = null;
			iterator.setInherent(true);
		}
		return e;
	}

	/**
	 * Return true if the given node is valid, i.e. it is a real node of the
	 * graph. <br>
	 * <br>
	 * <b>Note:</b> A Node pointing to a removed item could become valid again
	 * later if new nodes are added to the graph.
	 * 
	 * @param node
	 * @return true if the given node is valid
	 */
	public boolean valid(Node node) {
		return validNodeId(node.id);
	}

	protected boolean validNodeId(int id) {
		return id >= 0 && id < nodes.size() && nodes.get(id).previous != -2;
	}

	/**
	 * Return true if the given arc is valid, i.e. it is a real arc of the
	 * graph. <br>
	 * <br>
	 * <b>Note:</b> An Arc pointing to a removed item could become valid again
	 * later if new edges are added to the graph.
	 * 
	 * @param arc
	 * @return true if the given arc is valid
	 */
	public boolean valid(Arc arc) {
		return validArcId(arc.id);
	}

	protected boolean validArcId(int id) {
		return id >= 0 && id < arcs.size() && arcs.get(id).previousOut != -2;
	}

	/**
	 * Return true if the given edge is valid, i.e. it is a real edge of the
	 * graph. <br>
	 * <br>
	 * <b>Note:</b> An Edge pointing to a removed item could become valid again
	 * later if new edges are added to the graph.
	 * 
	 * @param edge
	 * @return true if the given edge is valid
	 */
	public boolean valid(Edge edge) {
		return validEdgeId(edge.id);
	}

	protected boolean validEdgeId(int id) {
		return id >= 0 && (2 * id) < arcs.size()
				&& arcs.get(2 * id).previousOut != -2;
	}

	/**
	 * Add a new node to the graph
	 * 
	 * @return the newly created node
	 */
	public Node addNode() {
		int n;
		InternalNode internalNode = null;
		// Increase the node count
		nodeNum++;
		// if there is not a free slot, allocate a new slot
		if (firstFreeNode == -1) {
			n = nodes.size();
			internalNode = new InternalNode(n);
			nodes.add(internalNode);
		}
		// if there is a free slot, reuse the object contained in the slot
		else {
			n = firstFreeNode;
			internalNode = nodes.get(n);
			// the next free node is the next node
			firstFreeNode = internalNode.next;
		}
		// the previous first node became the second
		internalNode.next = firstNode;
		if (firstNode != -1) {
			// if there was a previous node in the graph the current node
			// became its previous
			nodes.get(firstNode).previous = n;
		}
		// the current node became the first node
		firstNode = n;
		internalNode.previous = -1;
		// the new node doesn't have any edges
		internalNode.firstOut = -1;

		Node node = nodeFromId(n);
		for (AddNodeHandler<Node> handler : addNodeHandlers) {
			handler.onAddNode(node);
		}
		return node;
	}

	/**
	 * Add a new edge to the graph between the nodes u and v.
	 * 
	 * @param u
	 * @param v
	 * @return the newly created arc
	 */
	public Edge addEdge(Node u, Node v) {
		int n;
		InternalArc oppositeArc;
		InternalArc inherentArc;

		// Increase the arcs count
		arcNum += 2;
		// Increase the edge count
		edgeNum++;
		// Get the internal data associated with the nodes
		InternalNode internalV = nodes.get(v.id);
		InternalNode internalU = nodes.get(u.id);

		// if there are not free slot for arcs
		if (firstFreeArc == -1) {
			// create new internal structure for the two arcs
			// the even id arc is the opposite direction arc while
			// the odd id arc is the inherent direction arc
			n = arcs.size();
			oppositeArc = new InternalArc(n);
			inherentArc = new InternalArc(n | 1);
			arcs.add(oppositeArc);
			arcs.add(inherentArc);
		} else {
			// otherwise reuse the two arcs of the free slot
			// note: each free slot is a tuple of arcs
			n = firstFreeArc;
			oppositeArc = arcs.get(firstFreeArc);
			// firstFreeArc | 1 == firstFreeArc + 1 when
			// firstFreeArc is even (as it should always be)
			inherentArc = arcs.get(firstFreeArc | 1);
			firstFreeArc = oppositeArc.nextOut;
		}

		// associate node targets
		oppositeArc.target = u.id;
		inherentArc.target = v.id;
		// the next outgoing arc of the current arc will be the old first
		// outgoing arc of v and the previous of the old first outgoing arc
		// of v, if one already existed, will be the current arc
		oppositeArc.nextOut = internalV.firstOut;
		if (internalV.firstOut != -1) {
			arcs.get(internalV.firstOut).previousOut = n;
		}
		// the current arc became the new first outgoing arc of v
		oppositeArc.previousOut = -1;
		internalV.firstOut = n;

		// the same applies for the inherent arc and its source u
		inherentArc.nextOut = internalU.firstOut;
		if (internalU.firstOut != -1) {
			arcs.get(internalU.firstOut).previousOut = (n | 1);
		}
		inherentArc.previousOut = -1;
		internalU.firstOut = (n | 1);

		Edge edge = arcFromId(n).edge();
		for (AddEdgeHandler<Edge> handler : addEdgeHandlers) {
			handler.onAddEdge(edge);
		}
		for (AddArcHandler<Arc> handler : addArcHandlers) {
			handler.onAddArc(inherentArc.getArc(), oppositeArc.getArc());
		}
		return edge;
	}

	/**
	 * Erase a node from the graph.
	 * 
	 * @param node
	 *            the node to be erased
	 */
	public void erase(Node node) {
		IncidentEdgeIterator<Edge> edge = new nl.vu.few.ibivu.jlemon.IncidentEdgeIterator<Edge>(this, node);

		// remove all incident edges
		while (edge.hasNext()) {
			erase(edge.next());
		}

		for (EraseNodeHandler<Node> handler : eraseNodeHandlers) {
			handler.onEraseNode(node);
		}

		// decrease the node count
		nodeNum--;
		// retrieve the internal node data of the node
		InternalNode n = nodes.get(node.id);

		// if the node has next node associate the previous of the next node
		// with the previous node
		if (n.next != -1) {
			nodes.get(n.next).previous = n.previous;
		}

		// if the node has a previous node, associate the next of the previous
		// node
		// with the next node
		if (n.previous != -1) {
			nodes.get(n.previous).next = n.next;
		}
		// ..else the next node is the new first node
		else {
			firstNode = n.next;
		}

		// the next node will be the old first free node
		n.next = firstFreeNode;
		// the current node is the head of the list of free nodes
		firstFreeNode = node.id;
		// no need to double link the list of free nodes
		n.previous = -2;
	}

	/**
	 * Erase an edge from the graph.
	 * 
	 * @param node
	 *            the node to be erased
	 */
	public void erase(Edge edge) {
		int n = edge.id * 2;
		// obtain the corresponding opposite and inherent arcs
		InternalArc o = arcs.get(n);
		InternalArc i = arcs.get(n | 1);

		for (EraseEdgeHandler<Edge> handler : eraseEdgeHandlers) {
			handler.onEraseEdge(edge);
		}
		for (EraseArcHandler<Arc> handler : eraseArcHandlers) {
			handler.onEraseArc(i.getArc(), o.getArc());
		}

		// decrease the arcs count
		arcNum -= 2;
		// decrease the edges count
		edgeNum--;

		// if the given arc is *not* the last of the list, associate the
		// previous of the next arc with the current previous
		if (o.nextOut != -1) {
			arcs.get(o.nextOut).previousOut = o.previousOut;
		}

		// if the given arc is not the first of the list, associate the next of
		// the of previous arc with the current next
		if (o.previousOut != -1) {
			arcs.get(o.previousOut).nextOut = o.nextOut;
		}
		// if it is the first of the list, associate the first arc out of
		// the target node to the next node
		else {
			nodes.get(i.target).firstOut = o.nextOut;
		}

		// do the same for the inherent arc
		if (i.nextOut != -1) {
			arcs.get(i.nextOut).previousOut = i.previousOut;
		}

		if (i.previousOut != -1) {
			arcs.get(i.previousOut).nextOut = i.nextOut;
		} else {
			nodes.get(o.target).firstOut = i.nextOut;
		}

		o.nextOut = firstFreeArc;
		firstFreeArc = n;
		o.previousOut = -2;
		i.previousOut = -2;
	}

	public void clear() {
		for (ClearHandler handler : clearHandlers) {
			handler.onClear();
		}
		nodeNum = arcNum = edgeNum = 0;
		arcs.clear();
		nodes.clear();
		firstNode = firstFreeNode = firstFreeArc = -1;
	}

	/**
	 * Changes the end v of the given edge to node n. The <tt>EdgeIterator</tt>s
	 * and <tt>ArcIterators</tt>s referencing the changed edge are invalidated
	 * and if the changed node is the base node of an iterator then this
	 * iterator is also invalidated.
	 * 
	 * <b>Note:</b>This functionality cannot be used together with the Snapshot
	 * feature.
	 * 
	 * @param edge
	 * @param node
	 */
	public void changeV(Edge edge, Node node) {
		int a = 2 * edge.id;
		InternalArc o = arcs.get(a);
		InternalArc i = arcs.get(a | 1);
		InternalNode n = nodes.get(node.id);

		if (o.nextOut != -1) {
			arcs.get(o.nextOut).previousOut = o.previousOut;
		}
		if (o.previousOut != -1) {
			arcs.get(o.previousOut).nextOut = o.nextOut;
		} else {
			nodes.get(i.target).firstOut = o.nextOut;
		}

		if (n.firstOut != -1) {
			arcs.get(n.firstOut).previousOut = a;
		}
		i.target = node.id;
		o.previousOut = -1;
		o.nextOut = n.firstOut;
		n.firstOut = a;
	}

	/**
	 * Changes the end u of the given edge to node n. The <tt>EdgeIterator</tt>s
	 * and <tt>ArcIterators</tt>s referencing the changed edge are invalidated
	 * and if the changed node is the base node of an iterator then this
	 * iterator is also invalidated.
	 * 
	 * <b>Note:</b>This functionality cannot be used together with the Snapshot
	 * feature.
	 * 
	 * @param edge
	 * @param node
	 */
	public void changeU(Edge edge, Node node) {
		int a = 2 * edge.id;
		InternalArc o = arcs.get(a);
		InternalArc i = arcs.get(a | 1);
		InternalNode n = nodes.get(node.id);

		if (i.nextOut != -1) {
			arcs.get(i.nextOut).previousOut = i.previousOut;
		}
		if (i.previousOut != -1) {
			arcs.get(i.previousOut).nextOut = i.nextOut;
		} else {
			nodes.get(o.target).firstOut = i.nextOut;
		}

		if (n.firstOut != -1) {
			arcs.get(n.firstOut).previousOut = (a | 1);
		}
		o.target = node.id;
		i.previousOut = -1;
		i.nextOut = n.firstOut;
		n.firstOut = (a | 1);
	}

	/**
	 * Contracts two nodes. Node b will be removed but instead of deleting its
	 * incident edges, they will be joined to a. Edges forming loops will be
	 * removed.
	 * 
	 * @param a
	 * @param b
	 * @see #contract(Node, Node, boolean)
	 */
	public void contract(Node a, Node b) {
		contract(a, b, true);
	}

	/**
	 * Contracts two nodes. Node b will be removed but instead of deleting its
	 * incident edges, they will be joined to a.
	 * 
	 * <b>Note:</b>This functionality cannot be used together with the Snapshot
	 * feature.
	 * 
	 * @param a
	 * @param b
	 * @param removeLoops
	 *            if true edges forming loops will be removed
	 * @see #contract(Node, Node)
	 */
	public void contract(Node a, Node b, boolean removeLoops) {
		IncidentEdgeIterator<Edge> iterator = new nl.vu.few.ibivu.jlemon.IncidentEdgeIterator<Edge>(this, b);
		// loops through all the edge incident to node b
		while (iterator.hasNext()) {
			iterator.next();
			// if the user wants to remove loops and the current arc
			// points to a (the future source node) remove the edge
			if (removeLoops && v(iterator.peek()).equals(a)) {
				erase(iterator.peek());
			}
			// else if the source of the current edge is b then a
			// will be the new source
			else if (u(iterator.peek()).equals(b)) {
				changeU(iterator.peek(), a);
			}
			// else if the target of the current edge is b then a
			// will be the new target
			else {
				changeV(iterator.peek(), a);
			}
		}
		// remove the node b
		erase(b);
	}

	@Override
	public Class<Node> getNodeClass() {
		return Node.class;
	}

	@Override
	public Class<Arc> getArcClass() {
		return Arc.class;
	}

	@Override
	public Class<Edge> getEdgeClass() {
		return Edge.class;
	}
	
	@SuppressWarnings("serial")
	public class Edge implements nl.vu.few.ibivu.jlemon.concepts.Edge, Comparable<Edge>, Serializable {
		protected int id = -1;
		
		@Override
		public int compareTo(Edge edge) {
			if (this.id < edge.id) {
				return -1;
			}
			else if (this.id > edge.id) {
				return 1;
			}
			return 0;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + id;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			if (obj == null) {
				return false;
			}
			if (getClass() != obj.getClass()) {
				return false;
			}
			Edge other = (Edge) obj;
			if (id != other.id) {
				return false;
			}
			return true;
		}
	}

	@SuppressWarnings("serial")
	public class Arc implements nl.vu.few.ibivu.jlemon.concepts.Arc,
			Comparable<Arc>, HasEdge<Edge>, Serializable {
		protected int id = -1;
		protected Edge edge;

		@Override
		public Edge edge() {
			if (edge == null) {
				edge = new Edge();
				edge.id = (id == -1) ? -1 : (id / 2);
			}
			return edge;
		}

		@Override
		public int compareTo(Arc arc) {
			if (this.id < arc.id) {
				return -1;
			} else if (this.id > arc.id) {
				return 1;
			}
			return 0;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + getOuterType().hashCode();
			result = prime * result + ((edge == null) ? 0 : edge.hashCode());
			result = prime * result + id;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			if (obj == null) {
				return false;
			}
			if (getClass() != obj.getClass()) {
				return false;
			}
			Arc other = (Arc) obj;
			if (!getOuterType().equals(other.getOuterType())) {
				return false;
			}
			if (edge == null) {
				if (other.edge != null) {
					return false;
				}
			} else if (!edge.equals(other.edge)) {
				return false;
			}
			if (id != other.id) {
				return false;
			}
			return true;
		}

		private ListGraph getOuterType() {
			return ListGraph.this;
		}
	}

	@Override
	public void addClearHandler(ClearHandler handler) {
		clearHandlers.add(handler);
	}

	@Override
	public void addEraseArcHandler(EraseArcHandler<Arc> handler) {
		eraseArcHandlers.add(handler);
	}

	@Override
	public void addAddArcHandler(AddArcHandler<Arc> handler) {
		addArcHandlers.add(handler);
	}

	@Override
	public void addEraseNodeHandler(EraseNodeHandler<Node> handler) {
		eraseNodeHandlers.add(handler);
	}

	@Override
	public void addAddNodeHandler(AddNodeHandler<Node> handler) {
		addNodeHandlers.add(handler);
	}

	@Override
	public void addEraseEdgeHandler(EraseEdgeHandler<Edge> handler) {
		eraseEdgeHandlers.add(handler);
	}

	@Override
	public void addAddEdgeHandler(AddEdgeHandler<Edge> handler) {
		addEdgeHandlers.add(handler);
	}
}
